'''
https://leetcode.cn/problems/clone-graph/description/?envType=study-plan-v2&envId=top-interview-150
'''
from collections import deque


# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

from typing import Optional

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node: return node
        visted = {}
        def dfs(u):
            if u in visted: return
            visted[u] = Node(u.val)
            for v in u.neighbors:
                dfs(v)
                visted[u].neighbors.append(visted[v])
            return visted[u]
        return dfs(node)


    def cloneGraph2(self, node: Optional['Node']) -> Optional['Node']:
        if not node: return node
        dict = {node: Node(node.val)}
        q = deque([node])
        while q:
            u = q.popleft()
            for v in u.neighbors:
                if v not in dict:
                    dict[v] = Node(v.val)
                    q.append(v)
                dict[u].neighbors.append(dict[v])
        return dict[node]